Traditionally, Very Long Instruction Word (VLIW) processors have been defined by the following set of attributes. These processors have the ability to specify multiple, independent operations in each instruction (a MultiOp instruction.) VLIW architectures are horizontal machines, with each wide instruction-word or MultiOp, consisting of several operations or, Ops. All Ops in a MultiOp are issued in the same execution schedule. Programs that assume specific non-unit latencies for the operations and which, in fact, are only correct when those assumptions are true. The requirement for static, compile-time operation scheduling takes into account operation latencies and resource availability. Consequently, the hardware must conform exactly to the assumptions built into the program with regards to the number of functional units and the operation latencies. VLIW processors typically lack any interlock hardware, despite the fact that multiple, pipelined operations are being issued every cycle.
The original attraction of this style of architecture is its ability to exploit large amounts of instruction-level parallelism (ILP) with relatively simple and inexpensive control hardware. Whereas a number of VLIW products have been built which are capable of issuing six or more operations per cycle, it has just not proven feasible to build superscalar products with this level of ILP. Furthermore, the complete exposure to the compiler of the available hardware resources and the exact operation latencies permits highly optimized) schedules.
These very same properties have also led to the perception that VLIW processors are of limited interest as products. The rigid assumptions built into the program about the hardware are viewed as precluding object code compatibility between processors built at different times with different technologies and, therefore, having different latencies. Even in the context of a single processor, the need for the compiler to schedule to a latency, that is fixed at compile-time, is problematic with operations such as loads which can have high variability in their latency depending on whether a cache hit or miss occurs. Because of this latter problem, VLIW products have rarely adhered to the ideal of no interlock hardware, whatsoever. Alternatively, with an implementation of a VLIW architecture, interlocking and stalling of the processor is common when a load takes longer than expected.
The conventional wisdom is that dynamic scheduling is inapplicable to VLIW processors. A first step towards understanding how to perform dynamic scheduling on VLIW processors is to recognize the distinction between traditional VLIW processors and the concept of a VLIW architecture. A VLIW processor is defined by a specific set of resources (functional units, buses, etc.) and specific execution latencies with which the various operations are executed. If a program for a VLIW processor is compiled and scheduled assuming precisely those resources and latencies, it can be executed on that processor in an instruction-level parallel fashion without any special control logic. Conversely, a VLIW processor that has no special control logic can only correctly execute those programs that are compiled with the correct resource and latency assumptions. VLIW processors have traditionally been built with no special control logic and this has led to the conclusion that VLIW processors must necessarily be designed in this fashion.
A different view of VLIW is as an architecture, i.e., a contractual interface between the class of programs that are written for the architecture and the set of processor Implementations of that architecture. The usual view is that this contract is concerned with the instruction format and the interpretation of the bits that constitute an instruction. But the contract goes further and it is these aspects of the contract that are of primary importance in this patent. First, via its MultiOp capability, a VLIW architecture specifies a set of operations that are guaranteed to be mutually independent (and which, therefore, may be issued simultaneously without any checks being made by the issue hardware).
Second, via assertions about the operation latencies, an architecture specifies how a program is to be interpreted if one is to correctly understand the dependencies between operations. In the case of a sequential architecture, most latencies are assumed by the programmer to be a single cycle. So, the input operands for an operation must appear to that programmer to be determined by all the operations that were issued (and, in most cases, completed) before the operation in question. This is true because there are some sequential architectures, SPARC for example, where some instructions (branches with delay slots) have non-unit latencies.
In the case of programs for VLIW architectures, with operations having non-unit latencies, the input operands for an operation are not determined by all the operations that were issued before the operation in question. What matters is the operations that are supposed to have completed before the issuance of the operation in question. Operations that were issued earlier, but which are not supposed to have completed as yet, do not impose a flow dependence upon the operation in question.
A program has unit assumed latencies (UAL) if the semantics of the program are correctly understood by assuming that all operations in one instruction complete before the next instruction is issued. A program has non-unit assumed latencies (NUAL) if at least one operation has a non-unit assumed latency, L, which is greater than one, i.e., the semantics of the program are correctly understood if exactly the next L−1 instructions are understood to have been issued before this operation completes. An architecture is UAL (NUAL) if the class of programs that it is supposed to execute are UAL (NUAL). We shall use the terms NUAL program and latency-cognizant program interchangeably.
Very Long Instruction Word (VLIW) processors are viewed as an attractive way of achieving instruction-level parallelism because of their ability to issue multiple operations per cycle with relatively simple control logic. Although VLIW architectures offer the advantages of simplicity of design and high issue rates, a major impediment to the use of VLIW and other novel ILP architectures is that they are not compatible with the existing software base. Lack of object code compatibility in VLIW architectures across processors having different hardware latencies and varying levels of parallelism is a severe limit to their adoption as a general purpose computing paradigm. This means that an installed software base of binaries cannot be built around a family of generations. The economic implications of this problem are enormous, and an efficient solution is necessary if VLIW architectures are to succeed. Two classes of approaches to this problem have been reported in the literature: hardware approaches and software approaches. Although these techniques may provide compatibility, they do so at the expense of hardware complexity that can potentially impact cycle time. A typical software approach is to statically recompile the VLIW program from the object file. The approach generates multiple executables, which poses difficulties for commercial copy protection and system administration. For example, if a first generation of a machine has certain latencies involved with each functional unit and the second generation VLIW machine has different latencies involved with those same functional units, the old VLIW schedule cannot be guaranteed to execute properly on the second generation machine due to the flow dependence between the different operations. The same type of problem results if the second generation machine includes an additional functional unit. Even if the latencies remained the same, the code scheduled for this new machine would not execute correctly on the older machines because the scheduler has moved operations in order to take advantage of the additional functional unit. There is no trivial way to adapt this schedule to the older machines. This is the case of downward incompatibility between generations. In this situation, if different generations of the machines share binaries, compatibility requires either a mechanism to adjust the schedule or a different set of binaries for each generation. IBM describes hardware features for an ILP machine called DAISY (Dynamically Architected Instruction Set from Yorktown). DAISY is specifically intended to emulate existing architectures, so that all existing software for an old architecture (including operating system kernel code) runs without changes on the VLIW architecture. Each time a new fragment of code is executed for the first time, the code is translated to VLIW primitives, parallelized and saved in a portion of main memory not visible to the old architecture, by a Virtual Machine Monitor (software) residing in read only memory. Subsequent executions of the same fragment do not require a translation (unless cast out). A limitation of the hardware approaches is that the scope for scheduling is limited to the window of Ops seen at run-time, hence available ILP is relatively less than what can be exploited by a compiler. These schemes may also result in cycle time stretch, a phenomenon of concern when considering the VLIW paradigm over superscalar for future generation machines.
Instruction set architecture is a description of a computer architecture at the level the programmer can observe. A programmer's model of a computer architecture is a similar term. In an exposed-pipeline architecture, the delays associated with pipelined execution of instructions are visible in the instruction set architecture and can be exploited to improve computational bandwidth.
Other techniques of solving the compatibility issues involve migrating the software across to a new machine architecture. In these applications, oftentimes the original old architecture that is trying to be emulated, or the native instruction set architecture of a processor, is called the base architecture. The VLIW which emulates the old architecture, or any instruction set architecture, other than the base architecture of a given processor that will be supported on that processor, is called the migrant architecture.
Code compatibility between current and future generations of exposed pipeline VLIW DSPs is the example of compatibility reflected by this invention. For example, the TI C6000 DSP and the TI 64 bit C6000 DSP extension are the current and future architectures. The TI 64-bit C6000 DSP architecture contains changes in ISA visible pipelining and other architectural features to provide higher operating frequencies. These changes are reconciled with requirements for binary compatibility and a robust code migration path implemented with the invention below.